import collections
class Solution(object):
    def maximumPoints(self, edges, coins, k):
        d = collections.defaultdict(set)
        du = collections.defaultdict(int)
        for u, v in edges:
            d[u].add(v)
            d[v].add(u)

        def dfs(last_node, now_node):
            ans1 = coins[now_node] - k
            ans2 = coins[now_node] // 2
            up_dict = []
            if ans2 > 0:
                up_dict.append(ans2)
            for v in d[now_node]:
                if v != last_node:
                    r1, r_dict = dfs(now_node, v)
                    ans1 += r1
                    for value in r_dict:
                        if value > 1:
                            ans2 += value // 2
                            up_dict.append(value // 2)
            return max(ans1, ans2), up_dict

        return dfs(-1, 0)[0]
    





        
                


data = Solution()
edges = [[0,1],[1,2],[2,3]]
coins = [10,10,3,3]
k = 5
print(data.maximumPoints(edges, coins, k))